package com.tjetc.hw;

public class T01背包问题 {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int maxWeight = 4;
        int maxValue = f(weight,value,maxWeight,0);
        System.out.println(maxValue);
    }
    public static int f(int[] weight,int[] value,int maxWeight,int index){
        if(index==weight.length){
            return 0;
        }
        int no = f(weight,value,maxWeight,index+1);
        int yes = 0;
        if(maxWeight>=weight[index]){
            yes = value[index]+f(weight,value,maxWeight-weight[index],index+1);
        }
        return Math.max(no,yes);
    }
}
